package class10;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 *
 * 并查集:(证明花费: 1964-1989年, 结论:调用频繁复杂度O(1), 依赖的优化: 1.扁平化; 2.小挂大)
 * 1.有若干个样本a,b,c,d...类型假设是V
 * 2.在并查集中一开始认为每个样本都在单独的集合里
 * 3.用户可以在任何时候调用如下两个方法:
 * boolean isSameSet(V a, V b)  查样本x和样本y是否属于一个集合
 * void union(V a, V b)  把x和y各自所在集合的所有样本合并成一个集合
 * 4. isSameSet 和 union 方法的代价越低越好
 */
public class Code01_UnionFind {

	public static class Node<V> {
		V value;

		public Node(V v) {
			value = v;
		}
	}

	public static class UnionSet<V> {
		//映射关系: k=值  v=节点地址
		public HashMap<V, Node<V>> nodes;
		//映射关系: k=当前节点  v=父节点, 当父节点是自己时,那么当前节点是集合的代表点
		public HashMap<Node<V>, Node<V>> parents;
		//映射关系: k=集合代表点  v=集合代表点对应的集合元素个数
		public HashMap<Node<V>, Integer> sizeMap;

		public UnionSet(List<V> values) {
			//集合初始化时, 因无合并操作, 每个节点都是代表点, size=1
			for (V cur : values) {
				Node<V> node = new Node<>(cur);
				nodes.put(cur, node);
				parents.put(node, node);
				sizeMap.put(node, 1);
			}
		}

		// 从点cur开始，一直往上找，找到不能再往上的代表点，返回
		public Node<V> findFather(Node<V> cur) {
			Stack<Node<V>> path = new Stack<>();
			//找头节点
			while (cur != parents.get(cur)) {
				path.push(cur);
				cur = parents.get(cur);
			}
			// 这次查找路径的节点扁平化, 以便后续插叙速度提高
			// 更新一遍parents映射关系, 方便后续快速定位, 此时cur为头节点
			while (!path.isEmpty()) {
				parents.put(path.pop(), cur);
			}
			return cur;
		}

		public boolean isSameSet(V a, V b) {
			//已登记的样本才会查询是否
			if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
				return false;
			}

			return findFather(nodes.get(a)) == findFather(nodes.get(b));
		}

		public void union(V a, V b) {
			//未注册的key不合并
			if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
				return;
			}
			//找到头节点
			Node<V> aHead = findFather(nodes.get(a));
			Node<V> bHead = findFather(nodes.get(b));
			//不在同一个集合
			if (aHead != bHead) {
				//小集合头节点下挂到大集合头节点下, 减少遍历链的高度
				int aSetSize = sizeMap.get(aHead);
				int bSetSize = sizeMap.get(bHead);
				Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
				Node<V> small = big == aHead ? bHead : aHead;
				parents.put(small, big);
				//更新集合大小
				sizeMap.put(big, aSetSize + bSetSize);
				//小集合不再作为头节点
				sizeMap.remove(small);
			}
		}
	}

}
